#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

/*
typedef struct _List {
    int *sup;
    int size;
    int top;
    int tail;
} List;

List * ListInit(int size){
    List *l=malloc(sizeof(List));
    l->sup=malloc(sizeof(int)*(1+size));
    l->size=size+1;
    l->top=0;
    l->tail=0;
    return l;
}

bool ListEmpty(List *l){
    return (l->top == l->tail);
}

bool ListFull(List *l){
    return ( (l->tail+1)%l->size == l->top );
}

void Add(List *l,int e){
    l->sup[l->tail++]=e;
    l->tail=(l->tail)%l->size;
    return;
}

int  Del(List *l){
    int r=l->sup[l->top++];
    l->top=(l->top)%l->size;
    return r;
}*/

typedef int ElementType;
typedef struct _List{
    ElementType elm;
    struct _List *next;
    struct _List *tail;
} List;

List * ListInit(){
    List *l=malloc(sizeof(List));
    l->next=NULL;
    l->tail=l;
    return l;
}
bool ListEmpty(List *l){
    return (l->next==NULL);
}
bool ListFull(List *l){
    List *t=NULL;
    t=malloc(sizeof(List));
    free(t);
    return (t==NULL);
}
void Add(List *l,ElementType e){
    List *new=malloc(sizeof(List));
    new->elm=e;
    new->next=NULL;
    l->tail->next=new;
    l->tail=new;
    return;
}
ElementType Del(List *l){
    List *tmp=l->next;
    ElementType e=tmp->elm;
    l->next=tmp->next;
    free(tmp);
    if( !l->next )
        l->tail=l;
    return e;
}
List *Min(List *l){
    if ( !l->next )
        return NULL;
    l=l->next;
    int min=INT_MAX,last=l->elm;
    List *rl=NULL,*lastlist=l;
    l=l->next;
    while( l ) {
        if( min > last+l->elm ){
            rl=lastlist;
            min=last+l->elm;
        }
        last=l->elm;
        lastlist=l;
        l=l->next;
    }
    return rl;
}
List *MergeTwo(List *l){
    List *tmp=l->next;
    l->elm+=tmp->elm;
    l->next=tmp->next;
    free(tmp);
    return l;
}
int* supplyWagon(int* supplies, int suppliesSize, int* returnSize){
    List *l=ListInit();
    for( int i=0; i<suppliesSize; i++ )
        Add(l,supplies[i]);
    int r=(suppliesSize+1)>>1;
    for( int i=0; i<r; i++ ){
        MergeTwo(Min(l));
    }
    int rs=(suppliesSize)>>1;
    *returnSize=rs;
    int *ret=malloc(sizeof(int)*rs);
    int i=0;
    while( !ListEmpty(l) )
        ret[i++]=Del(l);
    return ret;
}

int main(){
    int rs;
    //int s[]={7,3,6,1,8};
    //int s[]={1,3,1,5};
    int s[]={9,10,9,9,4,1,7,6,6,4};
    int *r=supplyWagon(s,sizeof(s)/sizeof(int),&rs);
    printf("Return Size :%d\n",rs);
    for( int i=0; i < rs; i++ ){
        printf("%d ",r[i]);
    }
    return 0;
}
